#include<vector>
#include<deque>
using namespace std;


struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
 
class Solution {
    void dfs(deque<TreeNode*>& deque, vector<int>& path, vector<vector<int>>& res) {
        if (deque.empty()) {
            res.push_back(path);
            return;
        }
        int size = deque.size();
        while (size-- > 0) {
            TreeNode* cur = deque.front();
            deque.pop_front();
            if (cur->left) deque.push_back(cur->left);
            if (cur->right) deque.push_back(cur->right);
            path.push_back(cur->val);
            dfs(deque, path, res);
            path.pop_back();
            if (cur->right)deque.pop_back();
            if (cur->left)deque.pop_back();
        }
    }
public:
    vector<vector<int>> BSTSequences(TreeNode* root) {
        if (root == NULL) return { {} };
        vector<vector<int>> res;
        vector<int>path;
        deque<TreeNode*>deque;
        deque.push_back(root);
        dfs(deque, path, res);
        return res;
    }
};